#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
	int maximumGap(const vector<int>& nums) {
		if (nums.size() < 2) {
			return 0;
		}
		
		int n = nums.size();
		int max_val = *max_element(nums.begin(), nums.end());
		int min_val = *min_element(nums.begin(), nums.end());
		int bucket_interval = max(1, (max_val - min_val)/(n - 1));
		int bucket_size = (max_val - min_val)/bucket_interval + 1;
	
		vector<pair<int, int>> bucket(bucket_size, {INT_MAX, INT_MIN});
		for (auto num : nums) {
			int idx = (num - min_val)/bucket_interval;
			bucket[idx].first = min(bucket[idx].first, num);
			bucket[idx].second = max(bucket[idx].second, num);
		}

		int max_interval = 0;
		int prev = -1;
		for (int i = 0; i < bucket_size; i++) {
			if (bucket[i].first == INT_MAX) continue;
			if (prev != -1) {
				max_interval = max(max_interval, bucket[i].first - bucket[prev].second);
			}
			prev = i;
		}
		
		return max_interval;
	}
};

int main()
{
	Solution().maximumGap({3, 6, 9, 1});
}
